Macchina di Turing probabilistica

Nella teoria della calcolabilità, una macchina di Turing probabilistica è una macchina di Turing non deterministica che sceglie a caso fra le transizioni disponibili in ogni fase secondo una determinata distribuzione di probabilità. Si può perfino restringere questa definizione a una macchina che sceglie a ogni passo tra due transizioni con una probabilità 1/2 per ciascuna.^[1].

Nel caso di uguali probabilità per le transizioni, può essere definita come una macchina di Turing deterministica che ha un'istruzione di "scrittura" aggiuntiva dove il valore della scrittura è distribuito uniformemente nell'alfabeto della macchina di Turing (generalmente, una uguale probabilità di scrivere un "1" o uno "0" sul nastro). Un'altra formulazione comune è semplicemente una macchina di Turing deterministica con un nastro aggiunto pieno di bit casuali e chiamato perciò nastro casuale.^[2].

Come conseguenza, una macchina di Turing probabilistica (diversamente da una macchina di Turing deterministica) può avere risultati stocastici; su una data entrata e un dato stato di istruzione, la macchina può avere tempi di esecuzione diversi, o può non arrestarsi affatto; inoltre, può accettare un input in un'esecuzione e rifiutare lo stesso input in un'altra esecuzione.

Perciò la nozione di accettazione di una stringa da parte di una macchina di Turing probabilistica può essere definita in modi diversi. Le varie classi di complessità randomizzate in tempo polinomiale che risultano da diverse definizioni di accettazione includono RP, co-RP, BPP e ZPP. Se restringiamo la macchina allo spazio logaritmico invece che al tempo polinomiale, otteniamo l'analogo RL, co-RL, BPL e ZPL. Se applichiamo entrambe le restrizioni, otteniamo RLP, co-RLP, BPLP e ZPLP.

La computazione probabilistica è critica, anche per la definizione della maggior parte delle classi dei sistemi di prova interattivi, nei quali la macchina verificatrice dipende dalla casualità per evitare di essere prevista e ingannata dalla potentissima macchina dimostratrice. Ad esempio, la classe IP è uguale a PSPACE, ma se la casualità è rimossa dal verificatore, ci resta solo NP, che non è conosciuta, ma è largamente ritenuta essere una classe considerevolmente più piccola.

Una delle questioni centrali della teoria della complessità è se la casualità aggiunga potenza; ossia, c'è un problema che può essere risolto in tempo polinomiale da una macchina di Turing probabilistica ma non da una macchina di Turing deterministica? O possono le macchine di Turing deterministiche simulare in maniera efficiente tutte le macchine di Turing probabilistiche con al massimo un rallentamento polinomiale? Quest'ultimo caso sembrerebbe il più realistico, il che implicherebbe P = BPP. La stessa domanda per lo spazio logaritmico invece del tempo polinomiale (è L = BPLP?) è ritenuta vera ancora più largamente. D'altro canto, la potenza che la casualità dà ai sistemi di prova interattivi, come pure ai semplici algoritmi che crea per problemi difficili come i test di primalità in tempo polinomiale e i test di connettività dei grafi nello spazio logaritmico, suggerisce che la casualità potrebbe aggiungere potenza.

Un computer quantistico è un altro modello di computazione che è intrinsecamente probabilistico.